package Leetcode;

/**
 * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
 */
public class test83 {

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            //当链表为空或者只有一个节点时，此时就没有重复元素，直接返回即可
            return head;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        //当cur走到null时，遍历结束
        while (cur != null) {
            if (prev.val!= cur.val){
                prev=prev.next;
                cur=cur.next;
            }
            while (cur!=null&&prev.val== cur.val){
                cur=cur.next;
            }
            //当cur指向了第一个值不等于prev的元素时
            //此时prev.next到cur之间全部都是待删除的元素
            prev.next=cur;
            prev=prev.next;
        }
        return head;
    }


    /**
     * 与第一中类似
     * @param head
     * @return
     */
    public ListNode deleteDuplicates1(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while (cur!=null){
            if (prev.val== cur.val){
                prev.next=cur.next;
                cur=cur.next;
            } else{
                prev=prev.next;
                cur=cur.next;
            }
        }
        return head;
    }
    /**
     * 使用递归思路
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        //从第二个节点开始的子链表的重复节点删除交给函数来处理
        head.next=deleteDuplicates2(head.next);
        if (head.val==head.next.val){
            return head.next;
        }
        return head;

    }
}